// 13.1.1　Brute-Force算法
// function indexOf(target, pattern) {
//     var i = 0, j = 0,
//     tLen = target.length,
//     pLen = pattern.length;
//     while (i < tLen && j < pLen) {
//       if (target[i] == pattern[j]) {
//         i++;
//         j++;
//       } else {
//         i = i - j + 1; // target的指针回退到上次搜索的后一位
//         j = 0;         // pattern的索引回退到开始位置 
//       }
//     }
//     return j === pLen ? i - j : -1;
//   }
//   console.log(indexOf('aadddaa', 'ddd'));

// 13.1.2　KMP算法
// 保存的是前缀的起始位置，因此又叫前缀数组
// 又因为它只在失配时才使用，因此又叫失配数组
// 1:
// function getMaxLength(pattern) {
//   var pmt = [0],// 只有一个字符肯定不匹配
//     i = 1,// 最长后缀字符串从1开始 
//     j = 0,// 前缀的指针
//     pLen = pattern.length;
//   while (i < pLen) {
//     if (pattern[i] == pattern[j]) {
//       pmt[i] = j + 1;
//       j++;
//       i++;
//     } else {
//       pmt[i] = 0;
//       if (j === 0) {          
//         i++;
//       } else {
//         j = pmt[j - 1];
//       }
//     }
//   }
//   return pmt;
// }
// function indexOf(target, pattern) {
//   var pmt = getMaxLength(pattern),
//       i = 0, j = 0,
//       tLen = target.length,
//       pLen = pattern.length;
//   while (i < tLen && j < pLen) {
//     if (target[i] == pattern[j]) {
//       i++;
//       j++;
//     } else {
//       if (j == 0) {
//         i++; 
//       } else {// 失配
//         j = pmt[j - 1];// i不动，j从pmt中取
//       }
//     }
//   }
//   return j === pLen ? i - j : -1;
// }
// console.log(indexOf('aadddaa', 'ddd'));
// 2:
// function getNext(pattern) {
//   var next = [-1, 0],// 第一个值默认为-1, 第二个通过-1+1 = 0
//     i = 2,// 最大后缀字符串从2开始 
//     j = 0,// 前缀的指针
//     pLen = pattern.length;
//   while (i < pLen) {
//     if (pattern[i-1] == pattern[j]) {
//       next[i] = j + 1;
//       j++;
//       i++;
//     } else {
//       next[i] = 0;
//       if (j === 0) {
//         i++;
//       } else {
//         j = next[j];
//       }
//     }
//   }
//   return next;
// }
// // function getNext(pattern){
// //   var next = [-1],
// //     i = 0, 
// //     j = -1,
// //     pLen = pattern.length;
// //   while (i < pLen - 1) {// 第一位已经给出，只需要算len-1位
// //     if(j == -1 || pattern[i] == pattern[j] ){
// //       i++;
// //       j++;
// //       next[i] = j;
// //     }else{
// //       j = next[j];// 不匹配，j回退，寻找是否存在一个长度较小的字串和开头的字串相等
// //     }
// //   }
// //   return next;
// // } 
// function indexOf(target, pattern) {
//   var next = getNext(pattern);
//   var i = 0, j = 0;
//   var tLen = target.length;
//   var pLen = pattern.length;
//   while (i < tLen && j < pLen) {
//     // j == -1来自next数组的，没有意义，因此需要往后走
//     if (j == -1 || target[i] === pattern[j]) { // 命中
//       i++;
//       j++;
//     } else { // 未命中或失配
//       j = next[j];
//     }
//   }
//   return j === pLen ? i - j : -1;
// }
// function test(a, b) {
//   var c = indexOf(a, b);
//   var d = a.indexOf(b);
//   console.log(c, d, c === d);
// }
// test("AAADAABCDAB", "ABCDABD");
// test('aadddaa', 'ddd');
// test("mississippi", "issipi");// -1
// test('acabaabaabcacaabc', 'abaabcac');
// test('bbbbababbbaabbba', 'abb');
// test("BBC ABCDAB ABCDABCDABDE", "ABCDABD");
// console.log("BBC ABCDAB ABCDABCDABDE".indexOf("ABCDABD"));

// 2. nextval数组
// function getNextVal(pattern){
//   var nextval = [-1], i = 0, j = -1;
//   var pLen = pattern.length;
//   while(i < pLen-1){ // 第一位已经给出，只需要算len-1位
//     if (j == -1 || pattern[i] == pattern[j]) {
//       i++;
//       j++;
//       nextval[i] = pattern[i] == pattern[j] ? nextval[j]: j;
//     } else{
//       j = nextval[j];
//     }
//   }
//   return nextval;// 前缀数组或失配数组
// }
// function indexOf(target, pattern) {
//   var nextval = getNextVal(pattern);
//   var i = 0, j = 0;
//   var tLen = target.length;
//   var pLen = pattern.length;
//   while (i < tLen && j < pLen) {
//     if (j == -1 || target[i] === pattern[j]) { // 命中
//       i++;
//       j++;
//     } else { // 未命中或失配
//       j = nextval[j];
//     }
//   }
//   return j === pLen ? i - j : -1;
// }
// console.log(indexOf("AAADAABCDAB", "ABCDABD"));
// console.log(indexOf('aadddaa', 'ddd'));

// 13.1.3　多模式匹配算法
// function Node(value) {
//   this.value = value;
//   this.endCount = 0;
//   this.children = {};
// }
// class Trie {
//   constructor() {
//     this.root = new Node('root');
//   }
//   insert(word) {
//     var cur = this.root;
//     for (var i = 0; i < word.length; i++) {
//       var c = word[i];
//       var node = cur.children[c];
//       if (!node) {
//         node = cur.children[c] = new Node(word[i]);
//       }
//       cur = node;
//     }
//     cur.pattern = word; // 防止最后收集整个字符串用
//     cur.endCount++;     // 这个字符串重复添加的次数
//   }
// }
// function createGoto(trie, patterns) {
//   for (var i = 0; i < patterns.length; i++) {
//     trie.insert(patterns[i]);
//   }
// }
// function createFail(ac) {
//   var root = ac.root;
//   var queue = [root]; // root所在层为第0层
//   while (queue.length) {
//     // 广度优先遍历
//     var node = queue.shift();
//     if (node) {
//       // 将其孩子结点逐个加入队列
//       for (var i in node.children) {
//         var child = node.children[i];
//         if (node === root) {
//           child.fail = root; // 第1层结点的fail总是指向root
//         } else {
//           var p = node.fail; // 第2层以下的结点，其fail是在另一个分支上
//           while (p) {
//             // 遍历它的孩子结点，看它们有没有与当前孩子结点相同字符的结点
//             if (p.children[i]) {
//               child.fail = p.children[i];
//               break;
//             }
//             p = p.fail;
//           }
//           if (!p) {
//             child.fail = root;
//           }
//         }
//         queue.push(child);
//       }
//     }
//   }
// }
// function match(ac, text) {
//   var root = ac.root, p = root, ret = [], unique = {};
//   for (var i = 0; i < text.length; i++) {
//     var c = text[i];
//     while (!p.children[c] && p != root) {
//       p = p.fail; // 失配指针发挥作用
//     }
//     p = p.children[c];
//     if (!p) {
//       p = root; // 如果没有匹配的，从root开始重新匹配
//     }
//     var node = p;
//     while (node != root) {
//       //  收集出可以匹配的pattern
//       if (node.endCount) {
//         var pos = i - node.pattern.length + 1;
//         console.log(`匹配模式串 ${node.pattern}其起始位置在${pos}`);
//         if (!unique[node.pattern]) {
//           unique[node.pattern] = 1;
//           ret.push(node.pattern);
//         }
//       }
//       node = node.fail;
//     }
//   }
//   return ret;
// }

// var ac = new Trie();
// createGoto(ac, ["she", "shr", "say", "he", "her"]);
// createFail(ac);
// console.log(match(ac, "one day she say her has eaten many shrimps"));


// 13.2　回文算法

// function isPalindrome(s){
//   return s === s.split('').reverse().join('');
// }
// function isPalindrome(s){
//   var left = 0, right = s.length - 1;
//   while(left < right){
//     if(s[left] != s[right]){
//       return false;
//     }
//     left++;
//     right--;
//   }
//   return true;
// }
// console.log(isPalindrome('223322'));

// 13.2.1　中央扩展法
// function longestPalindrome(s) {
//   if (s.length <= 1) return s;
//   var layload = { sub: "", maxLen: 0 };
//   var n = s.length - 1; // 因为i+1，需要多留一个
//   for (var i = 0; i < n; i++) {
//     expandLen(s, i, i, n, layload); // 单核回文
//     expandLen(s, i, i + 1, n, layload); // 双核回文
//   }
//   return layload.sub;
// }
// function expandLen(s, low, high, n, layload) {
//   while (low >= 0 && high <= n) {
//     // 设置边界
//     if (s[low] == s[high]) {
//       if (high - low + 1 > layload.maxLen) {
//         layload.maxLen = high - low + 1;
//         layload.sub = s.substring(low, high + 1);
//       }
//       low--; // 向两边扩散找以当前字符为中心的最大回文子串
//       high++;
//     } else {
//       break;
//     }
//   }
// }
// console.log(longestPalindrome("babad"));// bab
// console.log(longestPalindrome("cbbd")); // bb

// 13.2.2　马拉车算法
// function preproccess(str) {
//   return "￥#" + str.split("").join("#") + "#";
// }

// function manacher(str) {
//   var res = preproccess(str),
//       right = 0,
//       center = 0,
//       maxLen = 1,
//       maxCenter = 0,
//       p = new Array(res.length).fill(0);
//   for (var i = 1; i < res.length; i++) {
//     // 存在匹配，在以中心点为半径的回文串中打镜像点
//     var mirror = 2 * center - i;
//     p[i] = i >= right ? 1 : Math.min(right - i, p[mirror]);
//     // 尝试继续向两边扩展，更新p[i]
//     while (res[i + p[i]] == res[i - p[i]]) {
//       p[i]++;
//     }
//     // 如果中心点加上其半径超出它的右边界，需要修改它的边界与中心
//     if (p[i] + i > right) {
//       right = p[i] + i;
//       center = i;
//     }
//     if (maxLen < p[i]) {
//       // 更新最大回文串的长度，并记下此时的中心点
//       maxLen = p[i];
//       maxCenter = i;
//     }
//   }
//   var start = (maxCenter - p[maxCenter]) >> 1;
//   return str.substring(start, start + maxLen - 1);
// }

// console.log(manacher("babaad")); // bab
// console.log(manacher("cbbd")); // bb
// console.log(manacher("mabakabat")); // abakaba
// console.log(manacher("abababb")); // ababa

// 13.2.3　回文自动机
// function Node(n, key) {
//   this.children = {};
//   this.endCount = 0; // 有多少个回文在这个字符串结束（如aba中的第2个a，就有2个）
//   this.len = n; // 回文长度
//   this.key = key; // 回文
//   this.count = 0; // 用于辅助统计原字符串有多少个回文
//   this.fail = null; // 用于跳转到不等于自身的最长后缀子串
// }

// class Palindromic {
//   constructor() { 
//     var evenRoot = new Node(0, '');// 偶数回文根
//     var oddRoot = new Node(-1, -1);// 奇数回文根
//     evenRoot.fail = oddRoot;
//     this.oddRoot = oddRoot;
//     this.evenRoot = evenRoot;
//     this.nodes = [evenRoot, oddRoot];
//     this.last = oddRoot;
//     this.chars = [-1]; // 开头放一个字符集中没有的字符，减少特判
//   }
//   getFail(node, n) {
//     var s = this.chars;
//     while (s[n - node.len - 1] != s[n]) { 
//       node = node.fail;  // 跳到另一棵树的结点中                    
//     }
//     return node;
//   }
//   extend(word) {
//     var k = this.chars.length;
//     for (var i = 0; i < word.length; i++) {
//       this.insert(word[i], i + k);
//     }
//   }
//   insert(c, n) {
//     this.chars.push(c);
//     var cur = this.getFail(this.last, n);
//     if (!cur.children[c]) {
//       var key = cur.len == -1 ? c : c + cur.key + c;
//       var node = new Node(cur.len + 2, key);// 新建结点
//       cur.children[c] = node;
//       this.nodes.push(node);
//       node.fail = cur.fail ? this.getFail(cur.fail, n).children[c] : this.evenRoot;
//       console.log('insert', key, node.fail.key); // only test
//       node.endCount = node.fail.endCount + 1;
//     }
//     var node = cur.children[c];
//     node.count++;
//     this.last = node;
//   }
//   count(){ // 统计原字符串有多少个回文
//     var nodes = this.nodes;
//     function el(i) {
//       return nodes[i];
//     }
//     var n = this.nodes.length;
//     for (var i = n - 1; i >= 2; --i) {
//       el(i).fail.count += el(i).count;
//     }
//     var num = 0;
//     for (var i = 2; i < n; i++) {
//       num += el(i).count;
//     }
//     return num;
//   }
// }
// var a = new Palindromic();
// a.extend('babbabc');
// console.log(a.count());// 12
// var b = new Palindromic;
// b.extend('abc');
// console.log(b.count());// 3
// var c = new Palindromic;
// c.extend('aaa');
// console.log(c.count());// 6
// var d = new Palindromic;
// d.extend('fdsklf');
// console.log(d.count());// 6

// 13.2.4　后缀自动机
// function Node(key){
//   this.key = key;
//   this.children = {}
// }
// var root = new Node("root");// 起点
// var a = root.children.a = new Node("a");
// var b = a.children.b = new Node("b");
// var c = b.children.c = new Node("c");
// var a1 = c.children.a = new Node("a"); 

// 3. 构建
function Node(key) {
  this.children = {};
  this.len = 0; // 最长子串的长度（该结点的子串数量=this.len - this.fail.len）
  this.isEnd = false;
  this.key = key; 
  this.fail = null;
  // this.num = 0;// 该状态子串的数量
  // this.count = 0; // 被后缀链接的个数，方便求结点字符串的个数
}

class SuffixAutomaton {
  constructor() {
    var node = this.root = this.last = new Node("");
    this.nodes = [node];
  }
  extend(word, cb) {
    cb = cb || function(){} // 用于为结点添加额外属性
    for (var i = 0; i < word.length; i++) {
      this.insert(word[i], cb);
    }
  }
  insert(c, cb) {
    cb = cb || function(){} // 用于为结点添加额外属性
    var p = this.last;
    var node = new Node(c);
    node.len = p.len + 1;
    this.last = node;
    this.nodes.push(node);
    cb(node, 'new');
    while (p && !p.children[c]) {
      // 如果p没有一条c的出边
      p.children[c] = node; 
      p = p.fail;
    }
    if (!p) {
      node.fail = this.root;
      cb(this.root, 'root');
    } else {
      var q = p.children[c];
      if (p.len + 1 == q.len) {
        node.fail = q;
        q.isEnd = true; // 主轴上冲突
        cb(q, 'main');
      } else {
        var clone = new Node(c); // 复制结点
        this.nodes.push(clone);
        clone.children = q.children;
        clone.fail = q.fail;
        clone.len = p.len + 1;
        clone.isEnd = true;
        cb(clone, 'branch', q);
        while (p && p.children[c] == q) {
          p.children[c] = clone; // 将树中所有q相关的链接替换成clone
          p = p.fail;
        }
        q.fail = node.fail = clone;
      }
    }
  }
}

// 4. 存在性查询
function contains(t, p) {
  if (t.length > p.length) {
    return false;
  }
  var sam = new SuffixAutomaton();
  sam.extend(p);
  var node = sam.root;
  for (var i = 0; i < t.length; i++) {
    var c = t[i];
    if (node.children[c]) {
      node = node.children[c];
    } else {
      return false;
    }
  }
  return true;
}
console.log(contains("cab", "abcabd"));// true   FIXTODO 实质打印是false
console.log(contains("abb", "abcabd"));// false

// 5. 不同的子串个数
// function count(p) {
//   var sam = new SuffixAutomaton();
//   sam.extend(p);
//   var ret = [];
//   function cb(node, c) {
//     for (var i in node.children) {
//       var key = c + i;
//       ret.push(key);
//       cb(node.children[i], key);
//     }
//   }
//   cb(sam.root, "");
//   console.log(ret);
//   return ret.length;
// }
// console.log(count("abb")); // 5
// console.log(count("abcabc")); // 15

// 6. 求两个字符串的最长公共子串
// function getLCS(a, b) {
//   var sam = new SuffixAutomaton();
//   sam.extend(a);
//   var node = sam.root, len = 0, max = 0;
//   for (var i = 0; i < b.length; i++) {
//     var c = b[i];
//     if (node.children[c]) {// 存在相同字符
//       len++;
//       node = node.children[c];
//     } else {
//       while (node && !node.children[c]) {
//         node = node.fail;
//       }
//       if (!node) {
//         node = sam.root;
//         len = 0;
//       } else {
//         len = node.len + 1;
//         node = node.children[c];
//       }
//     }
//     if (max < len) {
//       max = len;
//       // 知道当前结束位置i与子串的长度，求子串
//       lcs = b.substr(i - len + 1, len);
//     }
//   }
//   return lcs;
// }
// console.log(getLCS("uabcdefo", "dabcdui"));// abcd
// console.log(getLCS("alsdfkjffkdsal", "fdjskalajfkdsla"));// fkds

// 7. 求多个字符串的最长公共子串

// function getLCS(strs) {
//   var s = strs.shift();
//   var sam = new SuffixAutomaton();
//   sam.extend(s, function(node){
//     node.nlcs = Infinity; // 表示多个串的最小值
//     node.lcs = 0; // 表示当前匹配的最大值
//   });
   
//   var nodes = sam.nodes;
//   function compute(str) {
//     var len = 0, node = sam.root, max = 0;
//     for (var i = 0; i < str.length; i++) {
//       var c = str[i];
//       if (node.children[c]) {
//         len++;
//         node = node.children[c];
//       } else {
//         while (node && !node.children[c]) {
//           node = node.fail;
//         }
//         if (!node) {
//           len = 0;
//             node = sam.root;
//         } else {
//           len = node.len + 1;
//           node = node.children[c];
//         }
//       }
//       node.lcs = Math.max(node.lcs, len);
//     }
//     for (var i = 1; i < nodes.length; i++) {
//       var node = nodes[i];
//       node.nlcs = Math.min(node.nlcs, node.lcs);
//       node.lcs = 0;
//     }
//   }
//   var LCS = 0;
//   while (str = strs.shift()) {
//     compute(str);
//   }
//   var target = null;
//   console.log(nodes.length, 'nodes');
//   for (var i = 1; i < nodes.length; i++) {
//     var node = nodes[i];
//     if (node.nlcs > LCS) {
//       target = node;
//       LCS = node.nlcs;
//     }
//   }
//   var subLen = target.len;
//   console.log(s.slice(subLen - LCS, subLen));// 多串的公共子串（仅供测试）
//   return LCS;
// }
// console.log(getLCS([
//     "7uabcdefo",
//     "dabcdui",
//     "eeabc"])); // abc, 3
// console.log(getLCS([
//     "alsdfkjfjkdsal",
//     "fdjskalajfkdsla",
//     "fdjskjfajsdfdsf",
//     "aaaajfaaaa"
// ]));

// 8. 出现次数查询
// function timeOf(t, p) {
//   var sam = new SuffixAutomaton();
//   sam.extend(t, function (node, action, other) {
//     if (action === 'new') {
//       node.count = 1;
//     } else if (action === 'main') {// 主轴冲突
//       node.count++;
//     } else if (action === 'branch') {// 分支冲突，将clone的原结点的count+1
//       node.count = other.count + 1;
//     }
//   });
//   var node = sam.root, time = Infinity;
//   for (var i = 0; i < p.length; i++) {
//     var c = p[i];
//     var node = node.children[c];
//     if (node) {
//       time = Math.min(time, node.count);
//     }
//   }
//   var res = time === Infinity ? 0 : time;
//   console.log(`${p}在${t}中出现了${res}次`);
//   return res;
// }
// console.log(timeOf('abcdababc', 'abc'));
// console.log(timeOf('abcdababc', 'ab'));
// console.log(timeOf('abcdababc', 'da'));

// 10. 所有出现位置查询
// function allIndexOf(t, p) {
//   var sam = new SuffixAutomaton();
//   sam.extend(t, function (node, action) {
//     node.fails = [];
//     if (action === 'new') {
//       // pos为这个结点的字符在原字符串的位置 
//       node.pos = node.len - 1;
//     } else if (action === 'branch') {
//       // clone.pos就是刚添加的结点的pos
//       node.pos = sam.last.pos;
//     }
//   });
//   var nodes = sam.nodes;
//   for (var i = 1; i < nodes.length; i++) {
//     var node = nodes[i];
//     // 收集失配指针的另一个起点
//     if (node.fail.fails) {
//       node.fail.fails.push(node);
//     }
//   }
//   var node = sam.root, first = null;
//   for (var i = 0; i < p.length; i++) {
//     var c = p[i];
//     node = node.children[c];
//   }
//   var pos = [];
//   if (node) {
//     var count = [];
//     // 使用计数排序进行去重排序
//     node.fails && node.fails.concat(node).forEach(function (el) {
//       var value = el.pos - p.length + 1;
//       count[value] = 1;
//     });
//     for (var i = 0; i < count.length; i++) {
//       if (count[i] === 1) {
//         pos.push(i);
//       }
//     }
//     console.log(`${p}在${t}中出现的位置为${pos}`);
//     return pos;
//   } else {
//     console.log(`${p}不需要于${t}中`);
//     return pos;
//   }
// }
// console.log(allIndexOf('beededed', 'ed'));
// console.log(allIndexOf('abdabcabc', 'abc'));
// console.log(allIndexOf('abacdababca', 'a'));